package bfs;

public class 岛屿数量 {
	//将变量设计为static ，不要每次都创建，可以减少时间；
	public static int l,r;
    public static int MAXM=301;
    public static int MAXN=301;
    public static boolean[][] visit;
    public static int[] dx={1,-1,0,0};
    public static int[] dy={0,0,1,-1};
    public static int[][] queue=new int[MAXM*MAXN][2];

    //标记每块岛屿及其相邻的岛屿
    public static void bfs(char[][] grid,int i,int j,int l,int r){
    	l=r=0;
        queue[r][0]=i;
        queue[r++][1]=j;
        visit[i][j]=true;
        while(l<r){
            int size=r-l;
            for(int t=0;t<size;t++){
                int nx=queue[l][0];
                int ny=queue[l++][1];
                for(int k=0;k<4;k++){
                    int x=nx+dx[k],y=ny+dy[k];
                    if(x>=0&&x<grid.length&&y>=0&&y<grid[0].length&&visit[x][y]==false&&grid[x][y]=='1'){
                        visit[x][y]=true;
                        queue[r][0]=x;
                        queue[r++][1]=y;
                    }
                }
            }
        }
    }
    public int numIslands(char[][] grid) {
        int ret=0;
        int m=grid.length;
        int n=grid[0].length;
        visit=new boolean[MAXM][MAXN];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
            	//找岛屿的入口
                if(grid[i][j]=='1'&&visit[i][j]==false){
                    bfs(grid,i,j,l,r);
                    ret++;
                }
            }
        }
        return ret;
    }
}

